The present invention relates generally to electronic circuits and more particularly to adders for use in semiconductor integrated circuits and other electronic devices.
Adders are fundamental components of microprocessors, memory circuits, digital signal processors, communications hardware and numerous other electronic devices. The ever-increasing demand for higher speed and bandwidth in such devices requires that adders operate faster and support a longer word length.
In a conventional ripple-carry adder, a carry generated by an earlier adder stage is supplied to the next adder stage before the next stage can generate its carry. The carry propagation delay is therefore proportional to the number of stages in the adder.
A carry-skip adder provides reduced propagation delay relative to a ripple-carry adder by evaluating at a given adder stage each carry from the previous adder stages to determine if any stages can be skipped without affecting the addition result. The carry-skip adder is based on the principle that the carry propagation process can skip any adder stage j for which ajxe2x89xa0bj, where aj and bj denote the two binary numbers to be added in stage j. In other words, any adder stage j for which a propagate signal pj satisfies the condition pj=aj⊕bj=1 can be skipped. Several stages can be skipped if all such stages satisfy ajxe2x89xa0bj.
FIG. 1 shows an example of a conventional n-stage carry-skip adder 100. The n-stage adder 100 includes n k-bit ripple-carry adders 102-1, . . . 102-j, . . . 102-n, where 0 less than jxe2x89xa6n, and a set of carry-skip logic circuitry 104. The number k is also referred to as the block length of the carry-skip adder, and each of the ripple-carry adders are also referred to as carry-skip stages or simply stages. Each of the k-bit ripple-carry adders 102-i, i=1, 2, . . . n, receives corresponding partial inputs ai, bi, and generates a corresponding partial sum si. In addition, each of the ripple-carry adders 102-i other than the first adder 102-1 receives a corresponding primary carry input signal CINi generated by the carry-skip logic circuitry 104. The first stage 102-1 receives a first carry input C1. All of the ripple-carry adders 102-i other than the last adder 102-n supply a corresponding carry output signal COUTi to the carry-skip logic circuitry 104.
Each of the k-bit adders 102-i also generates a block-carry-propagate signal. For example, for the stage j adder 102-j the block-carry propagate signal is defined as:
Pjj+kxe2x88x921=pjxc2x7pj+1 . . . pj+kxe2x88x921, where k less than j.
The carry out COUTj of the k-bit adder 102-j may be expressed as
cj+k=Pjj+kxe2x88x921xc2x7cj+Gjj+kxe2x88x921
where Gjj+kxe2x88x921 is a block-generate signal for the adder 102-j.
Examples of conventional carry-skip adders are described in greater detail in U.S. Pat. No. 5,337,269 issued Aug. 9, 1994 in the name of inventors S. C. McMahan et al. and entitled xe2x80x9cCarry Skip Adder with Independent Carry-In and Carry Skip Paths,xe2x80x9d and U.S. Pat. No. 5,581,497 issued Dec. 3, 1996 in the name of inventor S. Kumar and entitled xe2x80x9cCarry Skip Adder with Enhanced Grouping Scheme,xe2x80x9d both of which are incorporated by reference herein.
It is generally desirable when designing a carry-skip adder to vary the block size k so as to optimize the carry propagation timing. In addition, it may also be possible to improve performance through the use of a multi-level skip.
Carry-skip adders are also often configured to include so-called split-adder logic. For example, many high speed communication and processing applications require an adder to perform full 32-bit additions as well as two parallel 16-bit additions. A conventional 32-bit carry-skip adder with split-adder logic uses a xe2x80x9csplitxe2x80x9d control signal to configure the adder to perform either a 32-bit addition or two parallel 16-bit additions.
FIG. 2 illustrates the manner in which the above-described split function is implemented for an n-bit carry-skip adder with a three-stage carry skip, where each xe2x80x9cstagexe2x80x9d in this context corresponds to a particular bit of the n-bit carry-skip adder. More specifically, FIG. 2 shows a portion of the (n/2+1)th carry-skip stage of the n-bit carry-skip adder. In the figure, a logic circuit 200 associated with this (n/2+1)th carry-skip stage includes a series arrangement of first level skip elements 202-1, 202-2 and 202-3. A carry CINj is applied to an input of the first level skip element 202-1. The carry outputs of the skip elements 202-1, 202-2 and 202-3 are denoted COUTA, COUTB and COUTC, respectively. Propagate signal outputs of the skip elements 202-1, 202-2 and 202-3 are denoted PA, PB and PC, respectively, and are applied to inputs of a three-input AND gate 204.
The AND gate 204 generates a propagate signal p(j:n/2+1) which is applied as a control signal to a control input of a two-to-one multiplexer 206. If the propagate signal has a value of logic zero, the output COUTC of the skip element 202-3 is passed through to the output of multiplexer 206 as the carry signal C(n/2+1). If the propagate signal has a value of logic one, the carry CINj is passed through to the output of multiplexer 206 as the carry C(n/2+1).
The carry C(n/2+1) is then applied to one input of a two-to-one multiplexer 208 as shown. The other input of the multiplexer 208 receives input carry C1. The output of the multiplexer 208 represents the input carry CINj+1 to the next stage of the carry-skip adder. The above-noted xe2x80x9csplitxe2x80x9d control signal is applied to the control input of the multiplexer 208. If the split control signal has a value of logic one, the carry-skip adder is operating as a 32-bit adder and the output carry is C1. If the split control signal has a value of logic zero, the carry-skip adder is operating as two parallel 16-bit adders, and the output carry is C(n/2+1). The multiplexer 208 thus serves as an additional multiplexing stage between the low and high half of the carry-skip adder, and is operative to pass along the carry C1 in a 32-bit addition or to zero the carry-in bit to the high word in the two parallel 16-bit addition case.
A significant problem with the above-described conventional arrangement for the incorporation of split-adder logic into a carry-skip adder is that the additional multiplexing stage results in an undesirable increase in the carry propagation delay. A need therefore exists for an improved approach which permits the incorporation of split-adder logic into a carry-skip adder without introducing additional propagation delay.
The present invention provides a carry-skip adder in which split-adder logic is incorporated without introducing additional propagation delay.
In accordance with the invention, an n-bit carry-skip adder includes a number of carry-skip stages and a logic circuit associated with one or more of the stages. The logic circuit includes split-adder logic and carry-skip logic configured such that a split control signal associated with the split-adder logic is applied to at least one gate of the carry-skip logic, so as to reduce a carry propagation delay of the adder. The gate of the carry-skip logic may be, for example, a gate which is also driven by a propagate signal of a carry-skip stage.
In an illustrative embodiment, the logic circuit is associated with an (n/2+1)th carry-skip stage of the adder, and the adder is configured to perform two parallel n/2-bit additions when the split control signal is at a first logic level, and to perform a single n-bit addition when the split control signal is at a second logic level.
The logic circuit in the illustrative embodiment may include a series arrangement of skip elements, a first one of the skip elements in the series receiving a first carry, and an output of a final one of the skip elements in the series representing a second carry. The propagate signal is generated as an output of a first logic gate, for example, a NAND gate, which receives as inputs the first carry and outputs of each of the skip elements.
The logic circuit in the illustrative embodiment also includes a multiplexer. More specifically, the first and second carries are applied to first and second signal inputs of a multiplexer having at least three signal inputs, and an input carry of the carry-skip stage is applied as a third carry to the third signal input. The multiplexer also has a plurality of control inputs for controlling selection of one of the first, second and third carries for propagation to an output of the multiplexer. A first one of the control inputs receives the split control signal, such that when the split control signal is at a first logic level, the third carry is propagated to the multiplexer output, and when the split control signal is at a second logic level, one of the first and second carries is propagated to the multiplexer output depending on a logic level of the propagate signal. Second and third control inputs receive outputs of second and third logic gates, respectively, each of these logic gates receiving one of a complemented or an uncomplemented version of the split control signal. As a result, when the split control signal is at the second logic level, the first carry is propagated to the output of the multiplexer if an output of the second logic gate is at the first logic level, and the second carry is propagated to the output of the multiplexer if an output of the second logic gate is at the first logic level.